// 文件名：multiset_leaderboard.cpp
// 目的：用 std::multiset 实现“排行榜”，按分数降序、用户名升序排序，支持同分多用户。
// 关键点：
//   - 自定义比较器 ScoreCompare：分数高者在前；分数相同按用户名字典序；
//   - multiset 允许重复“等价键”（相同分数与不同用户），适合作为多值有序集合；
//   - equal_range(Entry{score, ""})：获取所有指定分数的区间范围；
//   - lower_bound(Entry{score, ""})：用于定位某分数的首个位置（示例中删除最低分的一项）。
// 复杂度：
//   - 插入/删除/查找：O(log N)；遍历输出：O(N)。
// 注意：
//   - 比较器需满足“严格弱序”；若用户标识需唯一删除，生产中可用额外索引（如 map<user, iterator>）。

#include <iostream>
#include <set>
#include <string>

struct Entry {
    int score;
    std::string user;
};

// 自定义排序：分数降序；分数相同则用户字典序升序
struct ScoreCompare {
    bool operator()(const Entry& a, const Entry& b) const {
        if (a.score != b.score) return a.score > b.score;
        return a.user < b.user;
    }
};

int main() {
    // 初始化排行榜（自动按 ScoreCompare 排序）
    std::multiset<Entry, ScoreCompare> leaderboard = {
        {95, "alice"},
        {87, "bob"},
        {95, "claire"},
        {78, "dave"},
        {87, "eve"},
        {99, "frank"}
    };

    // 按排名输出（迭代顺序即为从高到低）
    std::cout << "Leaderboard (highest first):\n";
    int rank = 1;
    for (const auto& entry : leaderboard) {
        std::cout << "  #" << rank++ << " " << entry.user
                  << " -> " << entry.score << '\n';
    }

    // 查询：所有分数为 95 的用户（等价键范围）
    auto range = leaderboard.equal_range(Entry{95, ""});
    std::cout << "Users with score 95:";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << ' ' << it->user;
    }
    std::cout << '\n';

    // 更新：插入新成绩；删除一名最低分（示例用 lower_bound(78) 定位一项后擦除）
    leaderboard.insert({87, "grace"});
    leaderboard.insert({99, "hank"});
    leaderboard.erase(leaderboard.lower_bound(Entry{78, ""}));

    // 变更后输出
    std::cout << "After updates:\n";
    rank = 1;
    for (const auto& entry : leaderboard) {
        std::cout << "  #" << rank++ << " " << entry.user
                  << " -> " << entry.score << '\n';
    }

    return 0;
}